package cn.dai.test.da.linkedlist.singleLL;

import java.util.Stack;

/**
 * @author ArkD42
 * @file Jdbc01
 * @create 2020 - 06 - 07 - 17:39
 */
public class SingleLinkedList {

    // 定义头节点，且不存放任何数据
    private HeroNode the_head = new HeroNode(0," "," ");

    public HeroNode getThe_head() {
        return the_head;
    }

    // 尾部添加，节点
    public void add(HeroNode heroNode){
        // 不考虑编号顺序，直接找到当前链表最后的节点，该节点指向 新节点
        // 头节点不允许变换，使用临时节点辅助操作
        HeroNode tempNode = the_head;

        // 遍历判断，直到节点的下一节点为null，即表示最后节点
        while (true){
            if (tempNode .getThe_next() == null){
                // 找到了最后的节点，则注入节点
                tempNode.setThe_next(heroNode);
                break;
            }
            // 不是空说明不是最后一个,节点指向这个下一节点
            tempNode = tempNode.getThe_next();
        }
    }

    // 按着指定顺序进行插入
    public void addByOrder(HeroNode node){
        // 通过辅助的指针帮助我们完成插入
        HeroNode temp = the_head;

        // 设置标识编号判断，默认false，判断是否存在
        boolean existID = false;

        while(temp.getThe_next() != null){ // 等于空了就没有了
            if (temp.getThe_next().getNo() > node.getNo()) break;// 当前节点的下一节点的编号 大于注入节点的编号
            else if (temp.getThe_next().getNo() == node.getNo()) { // 编号存在了
                existID = true;
                break;
            }

            temp = temp.getThe_next();
        }

        if(existID) System.out.println("插入的英雄已经存在！！！");
        else {
            // 千万不要这样写，不然自己都傻了
            // node.getThe_next() = temp.getThe_next();
            // temp.getThe_next() = node;

            node.setThe_next( temp.getThe_next() );
            temp.setThe_next( node );
        }

    }

    // 展示链表
    public void show(){
        if (the_head.getThe_next() == null) {
            System.out.println("链表是空的！！！");
            return;
        }

        HeroNode temp = the_head;
        // 从头结点遍历，知道最后一个节点的下一节点是null
        while (temp.getThe_next() != null ) {
            temp = temp.getThe_next();
            System.out.println(temp);
        }
    }

    // 修改节点
    public void update(HeroNode newOne){
        if (the_head.getThe_next() == null) {
            System.out.println("链表为空");
            return;
        }

        HeroNode temp = the_head.getThe_next();

        while (temp != null){
            if (temp.getNo() == newOne.getNo()) {
                temp.setName( newOne.getName());
                temp.setAlias( newOne.getAlias());
                break;
            }
            temp = temp.getThe_next();
        }
    }


    public void delete(int no){
        HeroNode temp = the_head;

        while (temp != null){
            if (temp.getThe_next().getNo() == no){
                // 直接失去指向即表示删除了
                temp.setThe_next( temp.getThe_next().getThe_next() );
                break;
            }
            temp = temp.getThe_next();
        }
    }

    // ------------- 面试题案例 ---------------------------------------------

    // 求单链表的有效个数
    public int countNode(HeroNode headNode){
        if (headNode.getThe_next() == null) {
            System.out.println("链表为空");
            return -1;
        }
        int count = 0;

        HeroNode temp = the_head.getThe_next();

        while (temp != null){
            count ++;
            temp = temp.getThe_next();
        }
        return count;
    }

    // 查找倒数第n个节点
    public HeroNode theLastNodeIn(HeroNode head,int index){
        if (the_head.getThe_next() == null) return null;

        int size = countNode(head);
        if (index <= 0 || index > size) return null;

        HeroNode cursorNode = head.getThe_next();
        for (int i = 0; i < size - index; i++) {
            cursorNode = cursorNode.getThe_next();
        }

        return cursorNode;
    }

    // 单链表反转
    public void reverse(HeroNode headNode){
        if (headNode.getThe_next() == null || headNode.getThe_next().getThe_next() == null) return;

        HeroNode cursor = headNode.getThe_next();
        HeroNode the_next = null;
        HeroNode reverseHead = new HeroNode(0,"","");

        /*
        HeroNode
                cursor = headNode.getThe_next(),
                the_next = null,
                reverseHead = new HeroNode(0,"","");

         */

        while ( cursor != null){
            the_next = cursor.getThe_next();
            cursor.setThe_next( reverseHead.getThe_next() );
            reverseHead.setThe_next( cursor); // 最关键的连接步骤
            cursor = the_next;
        }

        headNode.setThe_next( reverseHead.getThe_next() );
    }

    // 栈结构实现逆序打印，利用先进后出的特点
    public void reversePrint(HeroNode head){
        if (head.getThe_next() == null) return;

        Stack<HeroNode> heroNodeStack = new Stack<>();

        HeroNode cursor = head.getThe_next();

        while ( cursor != null ){
            heroNodeStack.push( cursor );
            cursor = cursor.getThe_next();
        }

        while ( heroNodeStack.size() > 0){
            System.out.println(heroNodeStack.pop() );
        }
    }
}

